import java.util.Arrays;

public class changeNum2 {

        public static void main(String[] args) {
            int[] arr = {1, 2, 3, 4, 5, 6}; // 初始数组
            rearrangeAndSort(arr); // 调整数组并排序
            // 打印调整后的数组
            for (int num : arr) {
                System.out.print(num + " ");
            }
        }

        public static void rearrangeAndSort(int[] arr) {
            int n = arr.length;
            int left = 0, right = n - 1;

            // 先进行奇数和偶数的分离，双指针法
            while (left < right) {
                // 如果arr[left]是偶数，arr[right]是奇数，交换
                if (arr[left] % 2 == 0 && arr[right] % 2 != 0) {
                    // 交换
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                    left++;
                    right--;
                }

                // 如果arr[left]是奇数，向右移动left
                if (arr[left] % 2 != 0) {
                    left++;
                }

                // 如果arr[right]是偶数，向左移动right
                if (arr[right] % 2 == 0) {
                    right--;
                }
            }

            // 分别对奇数部分和偶数部分进行排序
            // 奇数部分的排序
            int[] oddArr = Arrays.copyOfRange(arr, 0, left);
            Arrays.sort(oddArr);

            // 偶数部分的排序
            int[] evenArr = Arrays.copyOfRange(arr, left, n);
            Arrays.sort(evenArr);

            // 将排序后的奇数和偶数数组合并回原数组
            System.arraycopy(oddArr, 0, arr, 0, oddArr.length);
            System.arraycopy(evenArr, 0, arr, oddArr.length, evenArr.length);
        }
}
